﻿//3113. 边界元素是最大值的子数组数目
//给你一个 正 整数数组 nums 。
//请你求出 nums 中有多少个子数组，满足子数组中 第一个 和 最后一个 元素都是这个子数组中的 最大 值。



class Solution {
public:
    long long numberOfSubarrays(vector<int>& nums)
    {
        //nums[i]==nums[j]    
        int n = nums.size();
        long long ans = n;
        stack<pair<int, int>> sta;
        sta.push({ INT_MAX,0 });
        for (int x : nums)
        {
            while (x > sta.top().first)
            {
                sta.pop();
            }
            if (x == sta.top().first)
            {
                ans += sta.top().second;
                sta.top().second++;
            }
            else
            {
                sta.push({ x,1 });
            }
        }
        return ans;
    }
};